package Aaaaaa;

import java.util.Arrays;
import java.util.Scanner;

public class Dijkstra {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int[][] value=new int[n+1][n+1];
        int[][] dis=new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j){
                    dis[i][j]=0;
                    value[i][j]=0;
                }else{
                    dis[i][j]=Integer.MAX_VALUE;
                    value[i][j]=Integer.MAX_VALUE;
                }
            }
        }
        for(int i=0;i<k;i++){
            int x=sc.nextInt();
            int y=sc.nextInt();
            int v=sc.nextInt();
            value[x][y]=v;
            value[y][x]=v;
            dis[x][y]=v;
            dis[y][x]=v;
        }
        search(value,dis,n);
        for(int i=0;i<=n;i++){
            System.out.println(Arrays.toString(dis[i]));
        }
    }

    private static void search(int[][] value, int[][] dis, int n) {
        for(int x=1;x<=n;x++){
            boolean[] flag=new boolean[n+1];
            flag[x]=true;
            int count=0;
            while(count<=n){
                int loc=0;
                int min=Integer.MAX_VALUE;
                for(int i=1;i<=n;i++){
                    if(!flag[i]&&dis[x][i]<min){
                        min=dis[x][i];
                        loc=i;
                    }
                }
                if(loc==0){
                    break;
                }
                flag[loc]=true;
                count++;
                for(int i=1;i<=n;i++){
                    if(!flag[i]&&value[loc][i]!=Integer.MAX_VALUE&&(dis[x][loc]+value[loc][i]<dis[x][i])){
                        dis[x][i]=dis[x][loc]+value[loc][i];
                    }
                }
            }
        }
    }
}
